package com.zhang.二叉树;

import java.util.Comparator;

/**
 * @author 张吉鑫
 * @Description 二叉搜索树
 * @date 2021/3/2 19:23
 */
public class BST<E>  extends BinaryTree<E> {

    protected Comparator<E> comparator;

    public BST() {
    }

    public BST(Comparator comparator){
        this.comparator = comparator;
    }
    /**
     * 添加元素
     * @param element
     */
    public void add(E element){
        elementNotNullCheck(element);
        if (root == null){
            root = createNode(element, null);
            size++;

            afterAdd(root);
            return;
        }
        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;
        while (node != null){
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0){
                node = node.right;
            }else if (cmp < 0){
                node = node.left;
            }else {
                node.element = element;
                return;
            }
        }
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0){
            parent.right = newNode;
        }else if (cmp < 0){
            parent.left = newNode;
        }
        size++;
        afterAdd(newNode);
    }

    /**
     * 删除元素
     * @param element
     */
    public void remover(E element){
        remover(node(element));
    }

    private void remover(Node<E> node){
        if (node == null){
            return;
        }

        size--;

        if (node.hasTwoChildren()){//度为2
            Node<E> p = predecessor(node);
            node.element = p.element;
            node = p;
        }

        Node<E> childNode = node.left != null ? node.left : node.right;

        if (childNode != null){//度为1
            childNode.parent = node.parent;
            if (childNode.parent == null){//如果删除的节点父节点是null 说明是根节点
                root = childNode;
            }else if (childNode.parent.left == node){
                childNode.parent.left = childNode;
            }else {
                childNode.parent.right = childNode;
            }
            afterRemove(node ,childNode);
        }else if (node.parent == null){//是叶子节点 又是根节点
            root = null;
            afterRemove(node , null);
        }else {//是叶子节点 度为0
            if (node.parent.left == node){
                node.parent.left = null;
            }else {
                node.parent.right = null;
            }
            afterRemove(node , null);
        }
//        afterRemove(node);
    }

    /**
     * 通过元素查找节点
     * @param element
     * @return
     */
    private Node<E> node(E element){
        elementNotNullCheck(element);

        if (root == null){
            return null;
        }

        Node<E> node = root;
        while (node != null){
            int cmp = compare(element, node.element);
            if (cmp == 0){
                return node;
            }else if (cmp > 0){
                node = node.right;
            }else {
                node = node.left;
            }
        }

        return null;
    }

    public boolean contains(E element){
        elementNotNullCheck(element);

        if (root == null){
            return false;
        }

        Node<E> node = root;
        int cmp = 0;
        while (node != null){
            cmp = compare(element, node.element);

            if (cmp > 0){
                node = node.right;
            }else if (cmp < 0){
                node = node.left;
            }else {
                return true;
            }
        }

        return false;
    }


    /**
     * 比较器
     * @param e1
     * @param e2
     * @return
     */
    private int compare(E e1 , E e2){
        if (comparator != null){
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>)e1).compareTo(e2);
    }

    /**
     * 判断元素是否为空
     * @param element
     */
    private void elementNotNullCheck(E element){
        if (element == null){
            throw new IllegalArgumentException("element must not be null!");
        }
    }

    protected void afterAdd(Node<E> node){ }

    protected void afterRemove(Node<E> node , Node<E> childNode){ }



}
